package leetcode;

import java.util.Arrays;

/**
 * @Description T279 完全平方数
 * @Author away
 * @Version V1.0.0
 * @Since 1.0
 * @Date 21.6.11
 */

public class T279 {
    public static void main(String[] args) {
        T279 t279 = new T279();
        t279.numSquares(2);
    }

    public int numSquares(int n) {
        int result = 0;
        int[] a = new int[(n >> 2) + 3];
        a[0] = 0;
        int num = 1;
        while (a[num - 1] < n) {
            a[num] = num * num;
            num++;
        }

        int[][] dp = new int[n + 1][num];

//        dp[n][n] = dp[n - a[num]] + 1;

        dp[1][1] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < num; j++) {
                int x = Integer.MAX_VALUE;
                int y = Integer.MAX_VALUE;
                if (i - a[j] >= 0) {
                    y = dp[i - a[j]][j] + 1;
                }
                if (j > 1) {
                    x = dp[i][j - 1];
                }
                dp[i][j] = Math.min(x, y);
            }
        }
        dp[n][0] = Integer.MAX_VALUE;
        result = Arrays.stream(dp[n]).min().getAsInt();
        return result;
    }
}
